package com.dong.ListNode.arithemtic;

/**
 * 设计双链表
 */

//双链表的定义
class ListNode3{
    int val;
    ListNode3 next;
    ListNode3 pre;
    ListNode3(int x) {val = x;}
}

public class LisNodeDemo3 {
    int size;
    //头结点，尾节点
    ListNode3 head;
    ListNode3 tail;

    //初始化链表
    public LisNodeDemo3() {
        size =0;
        head = new ListNode3(0);
        tail = new ListNode3(0);
        head.next = tail;
        tail.next = head;
    }

    //根据索引从双链表中取值
    public int get(int index) {
        ListNode3 current = head;
        if (index<0||index>size){
                return -1;
            }
            //index<(size-1)判断是头结点还是尾节点开始
            if (index<(size-1)/2){
                for (int i = 0; i < index; i++) {
                    current = head.next;
                }
            }
            else {
                for (int j = 0; j < size-index-1; j++) {
                    current = tail.pre;

                }
            }
            return current.val;
        }


    // 在第index个节点之前插入一个新节点
    public void addAtIndex(int index ,int val){
        if (size<index){
            return;
        }
        if (index<0){
            index = 0;
        }

        ListNode3 current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        ListNode3 newNode = new ListNode3(val);
        //双链表插入数据一共有处理四次
        newNode.next = current.next;
        current.next.pre = newNode;
        newNode.pre = current.pre;
        current.pre.next = newNode;
        size++;
    }

    //在链表的最前面插入以一个节点
    public void addAtIndex(int val){
        ListNode3 newNode = new ListNode3(val);
        ListNode3 cur = head;
        newNode.next = head.next;
        newNode = head.next.pre;
        cur.next = newNode;
        newNode.pre = cur;
        size++;
    }

    //在链表的最后面插入一个节点
    public void addTail(int val){
        ListNode3 newNode = new ListNode3(val);
        ListNode3 cur = tail;
        cur.pre =  tail.pre;
        cur = tail.pre.next;
        cur.next = tail;
        tail.pre = cur;
        size++;


    }





}
